/**
 * 121. 买卖股票的最佳时机
 */
public class Solution_121 {
    /**
     * 一次遍历
     * <p>
     * 时间复杂度：O(N)
     * <p>
     * 空间复杂度：O(1)
     */
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len < 2) {
            return 0;
        }

        // 初始化最大利润为 0，股票最低为第一天
        int maxProfit = 0, minPrice = prices[0];
        for (int i = 1; i < len; i++) {
            // 更新股票最低价
            minPrice = Math.min(prices[i], minPrice);
            // 更新最大利润
            maxProfit = Math.max(prices[i] - minPrice, maxProfit);
        }
        return maxProfit;
    }

    public static void main(String[] args) {
        Solution_121 solution = new Solution_121();
        int[] prices = { 7, 1, 5, 3, 6, 4 };
        int ans = solution.maxProfit(prices);
        System.out.println(ans);
    }
}